\newif\ifnotes
\notestrue

\documentclass[a4paper,11pt]{article}
\usepackage{breakcites}
\usepackage{fullpage}
\usepackage{amsmath, amsthm, times, amssymb}
\usepackage[table]{xcolor}
\usepackage[hypertexnames=false]{hyperref}
\usepackage{xspace}
\renewcommand{\paragraph}[1]{\vspace{1.5mm}\noindent \textbf{#1}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%general\
%\renewcommand{\vec}[1]{\mathbf{#1}}
\renewcommand{\cal}{\mathcal}
\newcommand{\bb}{\mathbb}
\newcommand{\ve}[1]{\langle #1 \rangle}
\newcommand{\samp}[1]{\overset{#1}{\leftarrow}}
\newcommand{\set}[1]{\left\{#1\right\}}
\newcommand{\abs}[1]{\left|#1\right|}
\newcommand{\labs}{\left |}
\newcommand{\rabs}{\right |}
\renewcommand{\)}{\right )}
\renewcommand{\]}{\right ]}
\renewcommand{\(}{\left (}
\renewcommand{\[}{\left [}
\newcommand{\pST}{\; \middle\vert \;}
\newcommand{\zo}{\{0,1\}}
\newcommand{\Nat}{\mathbb{N}}
\newcommand{\E}{\mathcal{E}}
\newcommand{\poly}{\mathrm{poly}}
\newcommand{\negl}{\mathrm{negl}}
\newcommand{\superpoly}{\mathrm{superpoly}}
\newcommand{\polylog}{\mathrm{polylog}}
\newcommand{\pprime}{p}
\newcommand{\zp}{\mathbb{Z}_\pprime}
\newcommand{\prot}[2]{\ve{#1,#2}}

% Languages and Relations
\newcommand{\lang}{\mathcal{L}}
\newcommand{\rell}{\mathcal{R}_\mathcal{L}}
\newcommand{\ins}{x}
\newcommand{\wit}{w}
\newcommand{\Time}{T}

%general algo
\newcommand{\secp}{n}
\newcommand{\Adv}{\mathsf{A}}
\newcommand{\Poly}{p}

%polynomail JP
\newcommand{\Tag}{\mathsf{Tag}}
\newcommand{\level}{k}
\newcommand{\llen}{\ell}
\newcommand{\vSet}{{\vec S}}
\newcommand{\Cir}{C}
\newcommand{\vCir}{{\vec C}}
\newcommand{\Csol}{D}
\newcommand{\inWire}{w_{in}}
\newcommand{\outWire}{w_{out}}
\newcommand{\Wire}{w}
\newcommand{\vWire}{v}
\newcommand{\uWire}{u}
\newcommand{\pGen}{{\sf Gen}}
\newcommand{\pVer}{{\sf Ver}}
\newcommand{\puz}{Z}
\newcommand{\xinp}{x}
\newcommand{\vxinp}{\vec x}



% Textual abbreviations (not for mathematical expressions)
\newcommand{\textabbrevstyle}[1]{\mbox{#1}}
\newcommand{\textabbrevstylebol}[1]{\mbox{\bf #1}}
\newcommand{\newtextabbrev}[1]{\expandafter\newcommand\csname #1\endcsname{\textabbrevstyle{#1}\xspace}}
\newcommand{\renewtextabbrev}[1]{\expandafter\renewcommand\csname #1\endcsname{\textabbrevstyle{#1}\xspace}}

\newcommand{\newtextabbrevbol}[1]{\expandafter\newcommand\csname #1\endcsname{\textabbrevstylebol{#1}\xspace}}
\newcommand{\renewtextabbrevbol}[1]{\expandafter\renewcommand\csname
#1\endcsname{\textabbrevstylebol{#1}\xspace}}

\newtextabbrev{OWF}
\newtextabbrev{PPT}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newtheorem{definition}{Definition}[section]
\newtheorem{lemma}{Lemma}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{theorem}{Theorem}[section]
\newtheorem{claim}{Claim}[section]
\newtheorem{assumption}{Assumption}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{hypothesis}{Hypothesis}[section]
\newtheorem{observation}{Observation}[section]
\theoremstyle{remark}
\newtheorem{construction}{Construction}[section]
\newtheorem{remark}{Remark}[section]
\newtheorem{example}{Example}[section]
\newtheorem{fact}{Fact}[section]
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newcommand{\secref}[1]{Section~\protect\ref{#1}}
\newcommand{\appref}[1]{Appendix~\protect\ref{#1}}
\newcommand{\defref}[1]{Definition~\protect\ref{#1}}
\newcommand{\assref}[1]{Assumption~\protect\ref{#1}}
\newcommand{\conref}[1]{Construction~\protect\ref{#1}}
\newcommand{\figref}[1]{Figure~\protect\ref{#1}}
\newcommand{\tblref}[1]{Table~\protect\ref{#1}}
\newcommand{\thmref}[1]{Theorem~\protect\ref{#1}}
\newcommand{\prpref}[1]{Proposition~\protect\ref{#1}}
\newcommand{\lemref}[1]{Lemma~\protect\ref{#1}}
\newcommand{\clmref}[1]{Claim~\protect\ref{#1}}
\newcommand{\corref}[1]{Corollary~\protect\ref{#1}}
\newcommand{\fctref}[1]{Fact~\protect\ref{#1}}
\newcommand{\eqnref}[1]{Equation~\protect\ref{#1}}
\newcommand{\algref}[1]{Algorithm~(\protect\ref{#1})}
\newcommand{\remref}[1]{Remark~\protect\ref{#1}}
\newcommand{\proref}[1]{Protocol~\protect\ref{#1}}
\newcommand{\stpref}[1]{Step~\protect\ref{#1}}
\newcommand{\tstref}[1]{Test~\protect\ref{#1}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newenvironment{boxfig}[2]{\begin{figure}[#1]\fbox{\begin{minipage}{\linewidth}
                        %\vspace{0.2em}
                        \makebox[0.025\linewidth]{}
                        \begin{minipage}{0.95\linewidth}
            {\small{
                        #2 }}
                        \end{minipage}
                        %\vspace{0.2em}
                        \end{minipage}}}{\end{figure}}


\newcommand{\pprotocol}[4]{
\begin{boxfig}{h!}{
\begin{center}
{\bf #1}
\end{center}
    #4
\vspace{0.5ex} } \caption{\label{#3} #2}
\end{boxfig}
}

\newcommand{\protocol}[4]{
\pprotocol{#1}{#2}{#3}{#4} }
%Example:
%\protocol{Header}{Caption}{label}{the protocol}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\ifnotes
\newcommand{\omer}[1]{$\ll$\textsf{\color{red} Omer: { #1}}$\gg$}
\newcommand{\amit}[1]{$\ll$\textsf{\color{orange} Amit: { #1}}$\gg$}
\else
\newcommand{\omer}[1]{}
\newcommand{\amit}[1]{}
\fi



\begin{document}
\author{
Omer Paneth\thanks{Boston University. Email: \texttt{omer@bu.edu}.  Supported by the Simons award for graduate students in theoretical computer science and an NSF Algorithmic foundations grant 1218461.}
\and
Amit Sahai\thanks{UCLA. Email: \texttt{sahai@cs.ucla.edu}.}
}


\title{Indistinguishability Obfuscation and Polynomial Jigsaw Puzzles}
\maketitle

\begin{abstract}
\end{abstract}

\thispagestyle{empty}
\newpage
\pagenumbering{arabic}
\section{Introduction}

\section{Polynomial Jigsaw Puzzles}
Polynomial jigsaw puzzles are closely related to multi-linear graded encodings \cite{GargGH13} and multi-linear jigsaw puzzles \cite{GargGH0SW13}.
A central component in the definition of polynomial jigsaw puzzles are arithmetic circuit with a curtin structure that we call set respecting. 

\begin{definition}[Set-respecting arithmetic circuits (\cite{PassTS13})]\label{def.set_respecting}
Given a level $\level \in \Nat$, and a vector of sets $\vSet \in (2^{[\level]})^\llen$, we say that an arithmetic circuit $\Cir$ taking $\llen$ inputs is $\vSet$-respecting if there exists a function $\Tag$ from the wires of $\Cir$ to $2^{[\level]}$ such that the following holds:
\begin{itemize}
\item For every $i\in[\llen]$, the $i$-th input wire $\inWire^i$ satisfies $\Tag(\inWire^i) = \vSet[i]$.
\item Every $+$ or $-$ gate in $\Cir$ connecting input wires $\uWire$ and $\vWire$ to an output wire $\Wire$, satisfies: 
$$\Tag(\uWire) = \Tag(\vWire) = \Tag(\Wire)\enspace.$$
\item Every $\times$ gate in $\Cir$ connecting input wires $\uWire$ and $\vWire$ to an output wire $\Wire$, satisfies 
$$\Tag(\uWire) \cap \Tag(\vWire) = \emptyset \quad \land \quad \Tag(\uWire) \cup \Tag(\vWire) = \Tag(\Wire)\enspace.$$
\item The output wire $\outWire$ satisfies $\Tag(\outWire) = [\level]$.
\end{itemize}
\end{definition}

\begin{definition}[Polynomial jigsaw puzzle]\label{def.PJP}
A polynomial jigsaw puzzle consists of a pair of \PPT algorithms $(\pGen,\pVer)$ satisfying the following properties:
\begin{description}
\item[Syntax and correctness.] 
For a pair of polynomial $\level = \level(\secp),\llen = \llen(\secp)$, the puzzle generation algorithm $\pGen$ is given as input a security parameter $1^\secp$, a vector of sets $\vSet \in (2^{[\level]})^\llen$ and a vector of $\secp$ arithmetic circuits:
    $$\vCir = \(\Cir_1,\dots \Cir_\secp\)\enspace,$$ 
    each taking $\llen$ inputs. $\pGen$ outputs a puzzle $\puz$. 
    The solution verification algorithm $\pVer$ takes a puzzle $\puz$ and an arithmetic circuit $\Csol$ with $\secp$ inputs and outputs a bit.
    
    For every vector of sets $\vSet$ and arithmetic circuits $\vCir,\Csol$ as above, let $\Csol_{\vCir}$ be the composed circuit:
    $$\Csol_{\vCir}(\vxinp) = \Csol(\Cir_1(\vxinp),\dots,\Cir_\secp(\vxinp))\enspace.$$
    We require that 
    $$\pVer(\pGen(1^\secp, \vSet, \vCir), \Csol) = 1\enspace,$$
    iff the circuit $\Csol_{\vCir}$ is $\vSet$-respecting and equivalent to the all-zero function. 
\item[Security.]
For every ensemble of sets vector and pairs of arithmetic circuits vectors: 
$$\set{\vSet_\secp, \(\vCir^1_\secp,\vCir^2_\secp\)}_{n \in \Nat}\enspace,$$ 
and for for every $\secp \in \Nat$ let:
$$\puz^1_\secp = \pGen(1^\secp, \vSet_\secp, \vCir^1_\secp) \quad,\quad \puz^2_\secp = \pGen(2^\secp, \vSet_\secp, \vCir^1_\secp)\enspace.$$

If for every arithmetic circuit $\Csol$ with $\secp$ inputs:
$$\pVer(\puz^1_\secp, \Csol) = 1 \quad \Leftrightarrow \quad \pVer(\puz^2_\secp, \Csol) = 1 \enspace,$$
then we require that:
$$\set{\puz^1_\secp}_{\secp \in \Nat} \approx_c \set{\puz^2_\secp}_{\secp \in \Nat}\enspace.$$

\end{description}
\end{definition}


 \bibliographystyle{alpha}
{
\bibliography{polynomial-jp}
}

\end{document}



